#include <stdio.h>
#include <stdlib.h>

typedef char E;

struct TreeNode1 {
    E element;
    struct TreeNode1 *left;
    struct TreeNode1 *right;
    int flag;
};

typedef struct TreeNode1 *Node;

//------------- 栈 -------------------
typedef Node T;   //这里栈内元素类型定义为上面的Node，也就是二叉树结点指针

struct StackNode {
    T element;
    struct StackNode *next;
};

typedef struct StackNode *SNode;  //这里就命名为SNode，不然跟上面冲突了就不好了

void initStack(SNode head) {
    head->next = NULL;
}

_Bool pushStack(SNode head, T element) {
    SNode node = malloc(sizeof(struct StackNode));
    if (node == NULL) return 0;
    node->next = head->next;
    node->element = element;
    head->next = node;
    return 1;
}

T peekStack(SNode head) {   //这里新增一个peek操作，用于获取栈顶元素的值，但是不出栈，仅仅是值获取
    return head->next->element;
}

_Bool isEmpty(SNode head) {
    return head->next == NULL;
}

T popStack(SNode head) {
    SNode top = head->next;
    head->next = head->next->next;
    T e = top->element;
    free(top);
    return e;
}

//----------------队列----------------
//typedef Node T;   //还是将Node作为元素

struct Queue0Node {
    T element;
    struct Queue0Node * next;
};

typedef struct Queue0Node * QNode;

struct Queue0{
    QNode front, rear;
};

typedef struct Queue0 * LinkQueue0_;

_Bool initQueue0(LinkQueue0_ Queue0){
    QNode node = malloc(sizeof(struct Queue0Node));
    if(node == NULL) return 0;
    Queue0->front = Queue0->rear = node;
    return 1;
}

_Bool offerQueue0(LinkQueue0_ Queue0, T element){
    QNode node = malloc(sizeof(struct Queue0Node));
    if(node == NULL) return 0;
    node->element = element;
    Queue0->rear->next = node;
    Queue0->rear = node;
    return 1;
}

_Bool isEmpty_q(LinkQueue0_ Queue0){
    return Queue0->front == Queue0->rear;
}

T pollQueue0(LinkQueue0_ Queue0){
    T e = Queue0->front->next->element;
    QNode node = Queue0->front->next;
    Queue0->front->next = Queue0->front->next->next;
    if(Queue0->rear == node) Queue0->rear = Queue0->front;
    free(node);
    return e;
}

//-----------------------------------

void preOrder(Node root) {
    struct StackNode head;
    initStack(&head);
    while (root || !isEmpty(&head)) {
        while (root) {
            printf("%c", root->element);
            pushStack(&head, root);
            root = root->left;
        }
        Node node = popStack(&head);
        root = node->right;
    }
    printf("\n");
}

void inOrder(Node root) {
    struct StackNode head;
    initStack(&head);
    while (root || !isEmpty(&head)) {
        while (root) {
            pushStack(&head, root);
            root = root->left;
        }
        Node node = popStack(&head);
        printf("%c", node->element);
        root = node->right;
    }
    printf("\n");
}

void postOrder(Node root) {
    struct StackNode stack;
    initStack(&stack);
    while (root || !isEmpty(&stack)) {   //其他都不变
        while (root) {
            pushStack(&stack, root);
            root->flag = 0;    //首次入栈时，只能代表左子树遍历完成，所以flag置0
            root = root->left;
        }
        root = peekStack(&stack);   //注意这里只是获取到结点，并没有进行出栈操作，因为需要等待右子树遍历完才能出栈
        if (root->flag == 0) {    //如果仅仅遍历了左子树，那么flag就等于0
            root->flag = 1;   //此时标记为1表示遍历右子树
            root = root->right;   //这里跟之前是一样的
        } else {
            printf("%c", root->element);   //当flag为1时走这边，此时左右都遍历完成了，这时再打印值出来
            popStack(&stack);   //这时再把对应的结点出栈，因为左右都完事了
            root = NULL;   //置为NULL，下一轮直接跳过while，然后继续取栈中剩余的结点，重复上述操作
        }
    }
    printf("\n");
}

void postOrder_D(Node root) {
    if (root == NULL) return;
    postOrder_D(root->left);
    postOrder_D(root->right);
    printf("%c", root->element);
}

void levelOrder(Node root){
    struct Queue0 queue0;   //先搞一个队列
    initQueue0(&queue0);
    offerQueue0(&queue0, root);  //先把根节点入队
    while (!isEmpty_q(&queue0)) {   //不断重复，直到队列空为止
        Node node = pollQueue0(&queue0);   //出队一个元素，打印值
        printf("%c", node->element);
        if(node->left)    //如果存在左右孩子的话
            offerQueue0(&queue0, node->left);  //记得将左右孩子入队，注意顺序，先左后右
        if(node->right)
            offerQueue0(&queue0, node->right);
    }
    printf("\n");
}

Node buildTree(){
    Node a = malloc(sizeof(Node));
    Node b = malloc(sizeof(Node));
    Node c = malloc(sizeof(Node));
    Node d = malloc(sizeof(Node));
    Node e = malloc(sizeof(Node));
    Node f = malloc(sizeof(Node));

    a->element = 'A';
    b->element = 'B';
    c->element = 'C';
    d->element = 'D';
    e->element = 'E';
    f->element = 'F';

    a->left = b;
    a->right = c;
    b->left = d;
    b->right = e;
    c->right = f;
    c->left = NULL;
    d->left = e->right = NULL;
    e->left = e->right = NULL;
    f->left = f->right = NULL;
    return a;
}

int main() {
    Node a = buildTree();
    printf("前序遍历 :");
    preOrder(a);
    printf("中序遍历 :");
    inOrder(a);
    printf("后序遍历1:");
    postOrder(a);
    printf("后序遍历2:");
    postOrder_D(a);
    printf("\n");
    printf("层序遍历 :");
    levelOrder(a);
}